package com.waiting.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 数组的全排列问题
 * @Author bjweitingting
 * @Date 2019/3/12
 **/
public class Arrangement {

    public static void main(String[] args) {
        int[] nums = {1};
        Arrangement arrangement = new Arrangement();
        List<List<Integer>> result = arrangement.permute(nums);
        for (List<Integer> item : result) {
            System.out.println(item.toString());
        }
    }

    /**
     * 数组的全排列
     * 数组中不包含重复元素的情况
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        genSubPer(nums, 0);
        return result;
    }
    //存储最终的排列结果
    List<List<Integer>> result = new LinkedList<>();

    void genSubPer(int[] nums, int start) {
        //递归出口
        if (start >= nums.length) {
            List<Integer> oneItem = new ArrayList<>(nums.length);
            for (int i = 0; i < nums.length; i++) {
                oneItem.add(nums[i]);
            }
            result.add(oneItem);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            //交换
            swap(nums, start, i);
            genSubPer(nums, start + 1);
            swap(nums, i, start);
        }
    }

    public void swap(int[] nums, int i, int j) {
        if (i >= nums.length || j >= nums.length) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
